String search algorithms are frequently employed for performing compression in data transmission systems. These algorithms, such as the various Lempel Ziv 77 algorithms, normally utilize a historical buffer containing a window of selected length of prior transmitted data against which incoming data is compared to find matches. The incoming data is then encoded as offsets and lengths based on such matches to achieve the desired compression. To facilitate the matching operation, hash tables are generally employed to identify a first potential match in the historical buffer and chain tables are frequently employed to identify additional potential matches.
Heretofore, in multichannel/multicontext environments (i.e. where a single node outputs different types of data to different receiving nodes with frames or packets of data for the different channels being interleaved) either completely separate data structures (i.e. a separate historical buffer, separate hash table and separate chain table) have been provided for each channel, or at least the history buffer portion of any shared data structure has been reset at the beginning of each frame. The first solution is disadvantageous in that it requires large amounts of memory. Since the various data structures must respond rapidly to assure that the compression operation does not adversely affect the data rate of the system, the memory used is expensive, high speed memory. Reducing memory requirements can therefore result in significant savings.
Resetting shared data structures after each frame, or at a minimum at the end of the last frame for a given data channel before transmission is switched to another channel, results in a need to build a new data structure, including a new history buffer, for each such frame. Since the more data there is in the history buffer, the higher the compression ratio which can be achieved, the frequent resetting of the various data structures, and in particular the resetting of the history buffer, results in significantly reduced average compression ratio for the systems.
It would therefore be desirable if memory requirements in a multichannel compression system could be reduced by sharing certain data structures, such as hash tables and chain tables, without the substantial loss in compression ratio caused by the resetting of data structures, and in particular history buffers, at frame or channel transitions.